//
//  SumOfLeftLeaves.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/9/19.
//  Copyright © 2020 WangYonghe. All rights reserved.
//

import UIKit

/*
 404. 左叶子之和
 
 计算给定二叉树的所有左叶子之和。

 示例：

     3
    / \
   9  20
     /  \
    15   7
 
 输入
 [3,9,20,null,null,15,7]

 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 */
/*
[1,2,null,3,null,4,null,5]
         1
        /
       2
      /
     3
    /
   4
  /
 5
 */
/*
 [0,2,4,1,null,3,-1,5,1,null,6,null,8]
 
 
 */

class SumOfLeftLeaves: NSObject {
    
    func sumOfLeftLeaves(_ root: TreeNode?) -> Int {
        
        return self.dfs(root)
    }
    
    func dfs(_ root: TreeNode?)->Int{
        
        if root?.left == nil && root?.right == nil{
            return 0
        }
        
        if root?.left != nil && root?.left?.left == nil && root?.left?.right == nil{
            return root!.left!.val + dfs(root?.right)
        }
        
        if root?.left != nil && root?.right != nil {
            return dfs(root?.left) + dfs(root?.right)
        }else if root?.left != nil && root?.right == nil{
            return dfs(root?.left)
        }else if root?.left == nil && root?.right !== nil{
            return dfs(root?.right)
        }
        return 0
    }
    
    //更简洁的写法参考
    /*
    var res = 0
    func sumOfLeftLeaves2(_ root: TreeNode?) -> Int {
        guard root != nil else {
            return 0
        }
        
        if root?.left != nil && root?.left?.left == nil && root?.left?.right == nil {
            res += root!.left!.val
        }
        return sumOfLeftLeaves2(root?.left) + sumOfLeftLeaves2(root?.right)
    }*/
}
